|
|
Component Interconnection Inference
Olšarová, Nela ; Rychlý, Marek (referee) ; Křivka, Zbyněk (advisor)
The Master Thesis deals with the design of hardware component interconnection inference algorithm that is supposed to be used in the FPGA schema editor that was integrated into educational integrated development environment VLAM IDE. The aim of the algorithm is to support user by finding an optimal interconnection of two given components. The editor and the development environment are implemented as an Eclipse plugin using GMF framework. A brief description of this technologies and the embedded systems design are followed by the design of the inference algorithm. This problem is a topic of combinatorial optimization, related to the bipartite matching and assignment problem. After this, the implementation of the algorithm is described, followed by tests and a summary of achieved results.
|
|
|
Multimodal System for Multi-Object Tracking in Real-Time
Kučera, Adam ; Šátek, Václav (referee) ; Rozman, Jaroslav (advisor)
This thesis deals with the topic of multi-object multi-sensor tracking. A conventional track-oriented multiple hypothesis tracking (TOMHT) pipeline is implemented in C++ programming language and an implementable interface is designed, enabling to easily extend the core algorithm with arbitrary sensors and measured target attributes, making the system multimodal, i.e.\ applicable in heterogeneous systems of sensors. A novel algorithm for solving combinatorial optimization arising in TOMHT is proposed. Finally, few example implementations of the interface are provided and the system is evaluated in simulated and real-world scenarios.
|
|
|
Traveling salesman problem with time windows
Pavlovič, Dávid ; Šoustek, Petr (referee) ; Dvořák, Jiří (advisor)
This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.
|
|
|
Experiments with the Swarm Intelligence
Hula, Tomáš ; Zbořil, František (referee) ; Grulich, Lukáš (advisor)
This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.
|
|
|
Probabilistic Neural Networks for Special Tasks in Electromagnetics
Koudelka, Vlastimil ; Tučková,, Jana (referee) ; Hartnagel, Hans Ludwig (referee) ; Raida, Zbyněk (advisor)
Tato práce pojednává o technikách behaviorálního modelování pro speciální úlohy v elektromagnetismu, které je možno formulovat jako problém aproximace, klasifikace, odhadu hustoty pravděpodobnosti nebo kombinatorické optimalizace. Zkoumané methody se dotýkají dvou základních problémů ze strojového učení a combinatorické optimalizace: ”bias vs. variance dilema” a NP výpočetní komplexity. Boltzmanův stroj je v práci navržen ke zjednodušování komplexních impedančních sítí. Bayesovský přístup ke strojovému učení je upraven pro regularizaci Parzenova okna se snahou o vytvoření obecného kritéria pro regularizaci pravděpodobnostní a regresní neuronové sítě.
|
|
|
Multimodal System for Multi-Object Tracking in Real-Time
Kučera, Adam ; Šátek, Václav (referee) ; Rozman, Jaroslav (advisor)
This thesis deals with the topic of multi-object multi-sensor tracking. A conventional track-oriented multiple hypothesis tracking (TOMHT) pipeline is implemented in C++ programming language and an implementable interface is designed, enabling to easily extend the core algorithm with arbitrary sensors and measured target attributes, making the system multimodal, i.e.\ applicable in heterogeneous systems of sensors. A novel algorithm for solving combinatorial optimization arising in TOMHT is proposed. Finally, few example implementations of the interface are provided and the system is evaluated in simulated and real-world scenarios.
|
|
|
Traveling salesman problem with time windows
Pavlovič, Dávid ; Šoustek, Petr (referee) ; Dvořák, Jiří (advisor)
This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.
|
|
|
Framework for development of optimization algorithms
Hurt, Tomáš ; Trunda, Otakar (advisor) ; Hric, Jan (referee)
The aim of the thesis is to design and implement an efficient tool for research and testing of algorithms of the combinatorial optimization. The domain of the planning research will be explained and the steps of design and implementation of such program will be covered. The framework will support two primary for- malisms for the description of optimization problems (PDDL, SAS+ ). The inputs processing will be provided, suitable data structures and efficient implementati- ons of search algorithms will also be included. The emphasis will be on a proper object design and easy extensibility for the future development. To achieve this goal, proven principles of software engineering will be used. 1
|
|
|
Artificial Bee Colony
Jukl, Jan ; Pangrác, Ondřej (advisor) ; Hušek, Radek (referee)
The minimum vertex cover (MVC) problem is a well-known NP-hard prob- lem. This thesis presents the Artificial Bee Colony (ABC) algorithm and two genetic algorithm approaches to solve this problem. The ABC algorithm is an optimization algorithm based on the intelligent behaviour of a honey bee swarm. It was first proposed for unconstrained optimization problems and showed that it is superior in performance on these kinds of problems. In this thesis, the ABC algorithm has been extended to solving the minimum vertex cover problem and applied to DIMACS and BHOSLIB benchmarks. The results produced by the ABC, the binary decision diagram based genetic algorithm and the MVC-aware genetic algorithm have been compared.
|
|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (advisor) ; Fellows, Michael R. (referee) ; Tantau, Till (referee)
In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity
|
guest ::
